#leetcode题目4：寻找两个正序数组的中位数
#难度：困难
#时间复杂度：O(log(min(m,n)))
#空间复杂度：O(1)
#解题思路：二分查找
#解题步骤：
#1. 首先判断两个数组的长度，如果nums1的长度小于nums2的长度，则交换两个数组
#2. 然后进行二分查找，找到中位数
#3. 如果找到中位数，则返回中位数

#TODO 暂时未正儿八经做过
class Solution:
    def findMedianSortedArrays(self,nums1,nums2):
        m,n=len(nums1),len(nums2)
        if m>n:
            nums1,nums2,m,n=nums2,nums1,n,m
        imin,imax,half_len=0,m,(m+n+1)//2
        while imin<=imax:
            i=(imin+imax)//2
            j=half_len-i
            if i<m and nums2[j-1]>nums1[i]:
                imin=i+1
            elif i>0 and nums1[i-1]>nums2[j]:
                imax=i-1
            else:   
                if i==0:
                    max_left=nums2[j-1]
                elif j==0:
                    max_left=nums1[i-1]
                else:
                    max_left=max(nums1[i-1],nums2[j-1])
                if (m+n)%2==1:
                    return max_left
                if i==m:
                    min_right=nums2[j]
                elif j==n:
                    min_right=nums1[i]
                else:
                    min_right=min(nums1[i],nums2[j])
                return (max_left+min_right)/2   

solution=Solution()


#测试数据
nums1 = [1,3]
nums2 = [2]
print(solution.findMedianSortedArrays(nums1,nums2))

nums1 = [1,2]
nums2 = [3,4]
print(solution.findMedianSortedArrays(nums1,nums2))